package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no45;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 1, 1, 1, 2, 1, 1, 1};
        System.out.println(solution.jump(nums));
    }

    public int jump(int[] nums) {
        if(nums.length <= 1){
            return 0;
        }
        // 跳跃最大步长
        int step = nums[0];
        // 跳跃起点
        int cur = 0;
        // 跳跃次数
        int jump = 0;
        while (true) {
            // 如果从当前位置可以直接跳到终点，直接次数+1，终止循环
            if(cur + step >= nums.length - 1){
                jump ++;
                break;
            }
            int max = Integer.MIN_VALUE;
            int maxIndex = 0;
            // 选择跳到 下次跳跃距离最远的一个格子
            for (int i = cur + 1; i <= cur + step && i < nums.length; i++) {
                if (i + nums[i] >= max && nums[i] != 0) {
                    max = i + nums[i];
                    maxIndex = i;
                }
            }
            // 跳跃次数加1，更新下次的起点和最大步长
            jump++;
            cur = maxIndex;
            step = nums[cur];
        }
        return jump;
    }


}
